算法评测在本地生活地图技术领域的探索和实践
作者：李佳慧、程睿、陈世强、秦宛霞、韩志强
这是阿里技术2022年的第41篇文章
（ 本文阅读时间：10分钟 ）
地图技术中使用到了大量业务数据和算法模型调优，为了解决算法可解释性弱、线下评测难等问题，我们在算法评测领域做了深入的探索和实践。本文将会详细介绍本地生活地图技术中的核心算法评测方案，以及为了提高算法评测效率，构建的评测平台和badcase分析工具。
01
地图技术在即时配送领域的应用
本地生活业务每天撮合千万量级的消费者和百万量级的商家之间的交易，物流(也称为”即时配送业务“)在其中的核心使命是在规定的时间、空间范围内，调度合适的骑手来高效履约完成运单。
物流是强依赖于空间元素，即本地生活的地图技术。本地生活业务时效性强，骑手在履约过程中，更多的使用的是骑、步行导航，对进入封闭区域（园区、小区、商圈等）的末端路网以及相应的导航精准度要求更高。本地生活业务有骑手履单及到取送的打点数据，这些信息的生产可以帮助高德补充骑步行以及封闭区域的末端路网，在此路网数据基础上，本地生活地图根据业务需求提供如下相关服务：
在饿了么app中的收餐地址，使用到地图的地址关键字搜索、周边搜索、地址实体命名识别NER(（Named Entity Recognition)以及地理编码服务NGC（New GeoCoding）等，帮助饿了么用户快速准确的选择收餐地址。从而提高了骑手运单履约效率，提升用户满意度；
基于路网上，构建骑手的骑步行路径导航：区域内末端路径规划，有效提升骑手的配送效率，缩短履约配送时长，提高用户体验；
订单的距离预估、时间预估也会应用到物流的智能调度中；
骑手取送餐点校准服务：对订单的取送餐地址进行精准的经纬度校准；
骑手履约异常单的判责：对于骑手报备的订单地址不准确，无法送达的异常情况，根据骑手位置和取送餐POI信息进行智能化判责；
地图技术中使用到大量业务数据、算法模型调优等，而算法的可解释性弱，线下评测难等问题，促使我们在算法评测领域做了深入的探索和实践。算法评测要求测试同学对业务、数据、以及算法有深入的理解，然后根据其特点，制定待评测算法的业务指标和技术指标，筛选相应的评测集，对待评测算法的服务进行批量请求和结果收集；按照指标维度对评测结果进行分析；对于产出的badcase进行归因分析；最终对待评测算法模型给出评测结论，帮助算法同学在上线前对算法模型的迭代效果有把控，缩短开发迭代周期。
接下来，本文会详细介绍本地生活地图技术中的核心算法评测方案，以及为了提高算法评测效率，构建的评测平台和badcase分析工具。
02
地址搜推 POI&AOI
2.1 业务介绍
POI（Point of Interest兴趣点，比如一栋楼、一个商店，医院，车站等）；AOI（Area of Interest兴趣面，一个区域状的地址位置实体，是一个封闭的多边形。例如：一个小区是一个AOI）。POI和AOI是描述用户、商户地理信息的基础数据，POI的准确度、覆盖度和新鲜度关系到饿了么C端收货地址搜推的准确性，也关系到物流中取送餐点精准度。物流侧的订单、商户、用户、配送范围等业务标签信息从AOI维度透出，帮助本地生活业务完成BCD联动以及活动的精细化运营。
地址搜推是饿了么app用户下单创建地址时使用，分两个场景，如下图所示：
周边搜：根据用户所在经纬度提供最可能的AOI和POI，并进行排序；
关键字搜索：根据用户输入关键字推荐AOI和POI，并进行排序；
目前地图侧有百万量级的AOI数据和千万量级的POI数据，每天进行更新，地址推荐的准确性会很大程度影响用户的下单体验。地址搜索推荐选取了用户戳点和POI距离、热度、类型以及父子POI个数等多维度的特征，选取算法模型做训练。用户点击地址具有很大的不确定性，在没有绝对预期结果的情况下，如何进行地址搜推模型评测是我们要解决的问题。
要在地址搜推模型上线前进行算法效果评估，需要和线上的模型效果监控指标对齐，地址搜推相关线上监控核心指标是地址搜推首条点击率，前三条点击率这些指标。经过和业务、算法同学讨论后，最终将线下评测指标定为MRR和TopN点击率。接下来我们要解决如何选取评测集，并使评测集能包含相对预期的地址搜推结果。通过挖掘和分析用户在饿了么app上地址搜推的埋点数据，目前方案是从用户下单时选择地址的埋点数据中获取用户点击的地址作为相对搜索预期结果，进行相关的指标评测。
2.2 评测指标设计
1）MRR
Mean Reciprocal Rank，该指标反应的是我们找到的这些item是否摆在用户更明显的位置，强调位置关系、顺序性。公式如下：
N表示推荐次数，p表示用户真实访问的item在推荐列表中的位置，如果没在推荐序列中，则p为无穷大，1/p为0；MRR的值越接近1，证明推荐的效果越接近用户预期。
2）TopN点击率
点击率目前统计用户点击在前1、3、5、10条的点击率，统计方式如下：
与MRR类似，该指标从用户角度更直观地体现算法的提升，作为业务侧更容易理解的指标，用户点击越前面证明该次推荐是更有效的推荐。
3）未召回率&召回率
推荐的AOI和POI列表中有无用户点击数据
该指标反映工程侧召回能力和数据完备性，若用户搜索和点击数据再返回结果中未找到，则很可能是POI、AOI数据缺失，若数据中有，则需要分析未召回的原因。
4）badcase以及badcase占比率
对比线上数据，排序位topN降低则作为badcase，算法模型调整后，导致排序变差的case是后续优化需要关注的场景。
2.3 评测集挖掘
从用户搜索、点击的埋点日志中抽取用户输入的地址关键字/所在经纬度，以及用户最终点击行为作为相对预期结果的评测样本集。评测集抽取按照不同的需求会有不同的分类：
作为日常回归的评测集，会有odps定时任务每天更新产出采样的评测集；
对于各类特殊场景，会积累相应的评测集：单字、特殊字符、错别字、地址、拼音搜索等各种类型的真实用户case；
对于评测运行产出的badcase集，我们会回流到评测集中，用于后面的评测。
2.4 评测方式
地址搜推模型的效果评测是以线上运行模型为基准，预发环境部署新的算法迭代模型，在相同的评测数据请求下，获取两个模型服务的返回结果，通过两两对比指标数据进行评测，最终也会对整体数据做指标汇总、报告产出以及badcase集产出。
具体方式如下：在评测平台中一次性接入地址搜推的评测场景；后面用户需要进行相关评测时，只需要选择相应的评测集，触发评测任务运行，评测平台会自动根据选择的CSV或odps的评测集，对线上模型和预发待评测模型的服务进行请求，运行后产出badcase集以及相应的评测报告。报告详情格式如下图：
03
地址识别 NGC&NER
3.1 业务介绍
饿了么app上使用的用户收货地址是二段式地址：第一段为搜索选定的地址（选定后会关联经纬度和城市信息），第二段为门牌号；这个两段式地址解析和经纬度绑定过程中，会使用到地图技术的NGC（new GeoCoding，新版地理编码服务）和NER（Named Entity Recognition，实体命名识别）算法服务，本节会介绍这两块业务以及相应的评测方案。两段式地址由用户自主填写，下面来看一些示例：
type | address | detailAddress | lng | lat | cityId |
正常地址 | 花港里社区东区x号楼 | x门xxx | xxx | xxx | xxx |
异常地址 | 义丰大路 | 义丰大路安国第一中学 | xxx | xxx | xxx |
重庆黔江区 | 重庆黔江区黔江西山转盘外贸局x单元xxx | xxx | xxx | xxx | |
遂昌县 | 遂昌县浙江省丽水市遂昌县妙高街道官碧路九弄x号楼xxx室 | xxx | xxx | xxx |
滑动查看表格
前面提到，经纬度(lng/lat)绑定的是address字段，异常地址如果不校准，骑手按照导航到达目标地点后，是无法直接送达的，需要电话与用户沟通确认，这就影响了配送效率，如果偏离真实地址较远，甚至会造成履约失败，引起用户、骑手和商家的投诉。为了解决这个问题，需要对异常地址进行校准，这就使用到了NGC地理编码服务，入参为用户当前地址信息（包括二段式地址、一段地址经纬度和城市），返回为用户真实地址经纬度坐标。
在NGC服务处理流程中，正确识别出二段式地址表达的关键信息，是精准召回用户真实坐标的关键，这里就使用到了NER实体命名识别算法，入参为地址性文本，返回为实体列表，每个实体包含文本、文本下标和类型信息。
为了评估NGC和NER算法效果，经过和产品、工程和算法同学讨论，最终明确了NGC算法的业务指标为订单维度POI准确率，技术指标为精确匹配召回率和符合预期的比例，NER算法的技术指标为实体类型的识别准召率和F1分数。
3.2 评测指标设计
1）订单维度POI准确率（NGC）
解释：NGC召回的点和骑手送达点，若距离在300/100/50米内，则认为准确。
分母：总订单量
分子：ngc能绑上的交付距离在300/100/50m内的订单量
说明：NGC能绑上使用NGC的绑定后经纬度结果，未能绑上使用原始经纬度，通过这些经纬度计算与骑手送达点的距离，计算300米、50米准确率。
2）技术指标（NGC）
poi召回率：poi召回结果占总样本的百分比；
超大poi占比/地址冲突型占比/地址互补型占比：poi召回结果中超大poi占比/地址冲突型占比/地址互补型占比；
精确匹配率：poi召回结果中精确匹配的概率；
0.5打分通过率：poi召回结果中打分不小于0.5概率；
es召回poi占比/gaia召回poi占比：poi召回结果中es/gaia占比。
3）技术指标（NER）
实体类别TP：被模型预测为正类的正样本
实体类别FP：被模型预测为正类的负样本
实体类别FN：被模型预测为负类的正样本
实体类别TN：被模型预测为负类的负样本
precision：被所有预测为正的样本中实际为正样本的概率
recall：在实际为正的样本中被预测为正样本的概率
accuracy：预测正确的结果占总样本的百分比
F1-Score：同时考虑精确率和召回率，让两者同时达到最高，取得平衡
3.3 评测集挖掘
1）NGC
评测集从订单埋点数据中提取地址信息作为入参，骑手送达点作为相对真值；订单埋点数据有通用POI表和超大POI表，通过时间、空间、量级等多维度筛选、字段转换，生成ngc_c/ngc_d通用POI评测集、ngc_c/ngc_d大POI评测集表；因为埋点数据中有骑手送达点字段，可直接用做相对真值，节省了人工标准成本。
2）NER
由于NER的实体类型属于语义理解范畴，目前业界尚没有完全自动化的真值标注方法，采用的是人工辅助校准模式。
3.4 评测方式
评测集构建完成后，上传到评测平台，新增评测场景，执行评测任务；评测任务同时并发访问预发待评测算法服务和线上在服务的算法接口，精确定位本次改动带来的版本差异case；如召回与真值不一致，记为badcase，其badcase集可以下载分析，并回流到评测集中，最终产出评测报告如下：
NER评测报告格式示例：
04
能力沉淀
针对前面章节对本地生活地图业务相关评测方案的介绍，我们对涉及到的算法评测场景归类分析后，经过长期的实践迭代，最终总结出了一套完整的评测方案如下：
制定评测指标：评测前要和业务、算法同学拉齐制定线下评测的指标，包括业务指标和技术指标等；
构建评测集：根据算法的特点和经验，挖掘评测样本数据，评测集的形式可能是存储在odps的一张表，也可以是csv/excel文件；
数据采集：发送评测集中的样本到待评测服务和线上服务/三方服务上，收集响应数据，待评测和待对比服务可以是HSF、HTTP或其他形式；
结果处理：响应数据收集完成后，需要根据要评测的指标，计算出每一个样本的明细数据；
产出报告：在所有明细都计算完成后，根据每个评测指标的统计规则，计算出每个指标的结果，并根据badcase的搜集逻辑统计badcase的明细数据，最后聚合在一起生成测试报告；
在评测方案的基础上，整个评测过程的自动化平台支撑是评测效率提升的关键。所以我们配套建设了评测平台，针对不同的业务特点，通过配置化接入上述流程中的各个节点，就可以在评测平台上快速接入一个算法评测场景，结合评测系统执行引擎，自动化的完成评测任务。
4.1 评测平台方案
平台分为交互和执行两大部分，交互层负责配置接入以及评测任务运维，执行层负责根据配置的内容通过状态机流转完成评测任务整个周期的执行。底层依赖Redis做任务同步和数据缓存，依赖MaxCompute平台能力完成数据明细的缓存和大数据计算，Mysql和Oss分别作为持久化存储，提供结果追溯能力；
Master+多agent模式：在跨环境（日常、预发、线上）采集分析数据方面，我们会针对不同环境搭建相应的执行agent，不同环境调用不同的agent执行器；最后针对不同的任务在MaxCompute中创建任务的分析表，用来存储对应任务全部待分析数据；
由于评测集样本量大，在待分析结果指标的大数据计算和执行效率方面，我们调用MaxCompute执行计算任务，解决了在计算和统计指标结果时需要加载全量数据并计算带来的内存和CPU压力。同时在任务的每个流程节点，都会分拆不同的子任务，通过多线程并发执行，最大程度的缩短执行时间；
为了快速接入和支持新增的算法模型评测，构建了通用配置化能力：通过配置样本表，数据分析表，SQL模板等方式来支持差异性问题。
4.2 Badcase分析工具
在算法评测产出badcase集后，算法和测试同学会在分析上花费很多时间，为了提高这块工作效率，我们在评测平台上配套建设了badcase快速根因分析的LiveDebug工具，帮助测试和算法同学快速定位问题。LiveDebug是基于google Dapper在搜推引擎中的一种实现，重点在于业务日志和算法日志信息的透出和诊断。例如：该工具在地址关键字搜推和周边搜中的应用，帮助算法定位和debug地址搜推算法过程中的相关问题，例如：地址召回后的算法模型筛选和排序。具体设计和实现如下：
05
结语
过去一年，我们在地图方向从无到有构建了算法评测体系，并建设了相应的效率平台，为本地生活地图业务的快速迭代和应用，起到了保驾护航的作用。随着地图技术越来越多的应用到本地生活业务中，我们的算法评测也会持续优化，让算法评测越来越智能化，同时拓展支撑更多的业务线：
评测集挖掘：目前已实现了基于本地生活业务离线数据去自动挖掘贴合线上流量特征的评测集，并且产出的评测集带了预期的标签，节省人工标注的成本。后续会尝试基于聚类算法等进行评测集的自动挖掘和生产；
Badcase归因分析：对于地址搜推类的badcase，目前有badcase分析工具支持问题的定位。但对于无法重现的场景，后续会尝试使用GBDT决策树模型做badcase的归因分析；
本地生活地图技术在不断拓展领域、迭代算法模型和提升算力，相应的评测工作也会继续拓展和支持；
除了地图领域，越来越多的智能调度等算法也在本地生活及时配送领域中应用，面向智能算法的质量保障也有无限的待探索空间。我们以地图业务的算法评测为起点，会持续在算法特征质量、埋点质量、离在线特征一致性，算法效果评测以及线上问题归因分析、新特征挖掘等方向继续探索。希望通过我们的努力，实现算法的可解释、可评测，让算法助力业务的过程更加透明。